package com.heima.leetcode.datastructure.linkedlist;

/**
 * 删除倒数第n个节点
 */
public class RemoveNthFormEnd {

    /**
     * <h3>方法一，递归</h3>
     * 给外界提供的删除倒数第n个节点
     *
     * @param head 链表的头节点
     * @param n    倒序索引n
     * @return 删除后的链表的头节点
     */
    public static ListNode removeNthFormEnd1(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head);
        int Nth = findEndNthRemove(sentinel, n);
        if (n < 0 || n >= Nth) {
            throw new IllegalArgumentException("参数 [" + n + "] 违法。");
        }
        return sentinel.next;
    }

    /**
     * <h3>方法二，快慢指针法</h3>
     * 目标是把p2快指针指到null并且把p1移到要删除的节点的前一个节点，那么移动完后，倒数第n个索引到p2要走n + 1次，所以倒数第n + 1个索引到p2要走n + 2次，所以一开始p2应比p1多走n + 2次
     *
     * @param head 旧链表的头节点
     * @param n    倒序索引n
     * @return 新链表的头节点
     */
    public static ListNode removeNthFormEnd2(ListNode head, int n) {
        if (head == null) {
            throw new IllegalArgumentException("链表为空");
        }
        ListNode sentinel = new ListNode(-1, head);
        ListNode p1 = sentinel;
        ListNode p2 = sentinel;
        for (int i = 0; i < n + 2; i++) {
            if (p2 == null || n < 0) { // 一定要放在前面，放在后面会把第一次指到null的情况也抛异常
                throw new IllegalArgumentException("参数 [" + n + "] 非法");
            }
            p2 = p2.next;
        }
        while (p2 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        p1.next = p1.next.next;
        return sentinel.next;
    }

    /**
     * 找到倒数第n个节点，如果n - 1个节点是要删除的节点，则删除
     *
     * @param head 链表的头节点
     * @param n    倒序索引n
     * @return 递归当前节点的倒序索引n
     */
    private static int findEndNthRemove(ListNode head, int n) {
        if (head.next == null) {
            return 0;
        }
        int Nth = findEndNthRemove(head.next, n);
        if (Nth == n) {
            head.next = head.next.next;
        }
        return Nth + 1;
    }
}
